One particularly useful application of the invention thus relates to the interleaving of data for error correction codes, especially of the LDPC (“Low Density Parity-Check Code”) or Turbo-Codes® type, in order to reduce the influence of errors on a noisy transmission channel.
Error correction codes of the LDPC or Turbo-Codes type are well-known in the state of the art.
Reference may thus be made to the prior French patent FR 91 05 280 which discloses the general principle of Turbo-Codes.
Said coding and decoding techniques are based on iterative processing of data which are mixed, at each processing stage, until succeeding in a decorrelation of the errors likely to be conveyed. Said error correction coding techniques use an interleaver that performs an iterative permutation of symbols of an input code and memory banks in which the data are stored.
FIG. 1 shows an example of architecture intended for the implementation of such data interleaving. As seen in this figure, the architecture shown is a parallel architecture. It comprises a set of data processing blocks or modules B1, B2, . . . Bn arranged in parallel ensuring, in parallel, the generation and deliverance of a set of binary symbols, a set of memory banks M1, M2, . . . Mn arranged in parallel and connected to the blocks B1, B2, . . . Bn with interposition of interconnection modules I1 and I2 intended for the parallel processing of the symbols coming from the blocks B1, B2, . . . Bn, for switching them to the memory banks M1, M2, . . . Mn by performing an iterative permutation of the symbol data in parallel.
One of the major problems associated with the implementation of this type of interleaving architecture relates to memory access conflicts. This is because, as seen in FIG. 2, with this type of architecture, it is possible that two or more blocks B1, B2, . . . Bn producing or using data may attempt to write or, on the contrary, to read different data at the same time into or from the same memory bank.
Various techniques have been developed to try to overcome this drawback. One of these techniques, disclosed in detail in the document FR 02 04 764, called “multiple slice turbo-code”, is based on the definition of a circular interleaving rule that can be used to implement an interleaver having a high degree of parallelism with performances equivalent to, or better than those of the known turbo-codes, whilst enabling the complexity of the interconnection architecture to be reduced, in particular for very high throughput applications.
The principle of multiple slice turbo-codes is based on splitting an information frame of N symbols into P blocks of M symbols. The coding operation is first performed in a natural order in order to generate a redundancy in a first dimension. Each block is then coded independently by a circular recursive systematic convolutional code (CRSC). The information frame is then permuted by an interleaver of N symbols in size. The interleaved frame is also split into P blocks of length N and each block is coded independently by a CRSC code to produce the redundancy in a second dimension.
The interleaver is constructed jointly with the memory organization so as to enable parallel decoding of the P blocks. In other words, the interleaver structure is chosen so as to enable the P data necessary to the P decoders of the P memory banks to be read and written at each cycle, without conflict.
Actually, a single reading may be performed at the same instant in a memory. However, this technique is based on the implementation of a specific interleaving rule and does not therefore conform to a standard.
Another technique, described in the document “SoC-Network for Interleaving in Wireless Communications” by N. Wehn, MPSoC, 2004, is based on an addition of memories into the network in order to provide a time delay of the data in the event of a conflict situation. However, this technique increases the latency of the circuit and produces complex interconnection networks. Furthermore, it is necessary to carry out the dimensioning of the added memories by simulation.
Finally, another approach, suggested by Benedetto and described in the article “Mapping Interleaving Laws to Parallel Turbo-decoder Architectures” published in IEEE volume 8, March 2004, consists in arranging the data in memory banks so as to avoid collisions. In particular, this approach suggests identifying the data which are intended to be used at the same time on a tiling matrix. A simple first assignment is made in the memory banks, without generating any conflict and a bank is assigned to the non-allocated data by correcting the conflicts using a so-called “simulated annealing” or “iterative refinement” method.
Although this technique can be used to find a memory arrangement whatever the interleaving rule, it nevertheless presents a certain number of major drawbacks, chiefly due to the fact that it does not enable a memory arrangement to be generated which can then be used to produce a hardware architecture using simple components, so that the interconnections network is liable to display a complicated architecture.
Furthermore, the simulated annealing algorithm is relatively complex to implement and does not allow its outcome to be determined a priori.
Finally, this technique requires the use of two ROM type memories per frame format for storing the natural and interleaved access orders in memory.